1. Field of the Invention
The present invention relates to on-line systems and methods for conducting auctions. More particularly, the present invention relates to on-line systems and methods for incorporating information about bidder budgets in multi-item sealed-bid auctions.
2. Description of the Related Art
There has recently been significant growth in the importance of dynamic pricing to market goods of many kinds. At the low end, eBay has clearly established the value of auctions for consumers to buy and sell individual items on the Internet. EBay has made important advances in many areas, including highly effective search, reputation and payment systems, dispute resolution and fraud prevention process, and others. Their auction design itself, however, remains unremarkable but effective, since most of the goods for sale are marketed one at a time. Auctions are conducted with a fixed deadline, and ascending bids are taken up to the deadline. A proxy bidder is available, and a particular variant, a Dutch auction design, is available for the small subset of items in which multiples units are available.
At the other extreme, auctions have been used effectively by the US and others to sell radio spectrum licenses, mineral rights and more, by financial houses to sell shares in firms and other investment instruments, and by web firms, most successfully Google, to sell advertisement space. Such auctions transact billions of dollars, often in highly complex, integrated and orchestrated events. The auctions are designed with the help of costly consultants, who write specialized rules to accommodate technical, regulatory and even political requirements. Bidders may also engage consultants to advise them on bid strategy. Personnel are assigned by both sides to full-time engagement during the auction events, which may involve weeks of effort. The auctioneer and their consultants train the bidders and maintain a ‘war room’ facility to manage the process. In the case of web ads, auctions are run in real-time and are exquisitely integrated with the ad delivery systems. Competition to provide services in these high-end auctions is intense.
Yet there are many market settings where auctions are not used because the methods just described are too costly. Nevertheless, these markets require the expression of business needs just like the larger ones, and have multiple goods for sale that can be substitutes or complements, or important business rules like constraints. Thus, there is a middle tier of governments and businesses that are not able to run efficient and effective auctions. In particular, there is a need for a radically lower cost and complexity of implementation for on-line auctions.
In multi-item auctions, budgetary limits can significantly limit a bidder's options: bidders often cannot risk outcomes where they may be required to pay more than their authorized budgets. Although important in many areas including online ad placement, an immediate need exists for auctions of heterogeneous physical goods, contracts, and financial instruments, where budget limits are important and existing auctions' failure to account for that reduce the number and level of bids. For example, in sales of oil and gas rights by the United States Department of the Interior, the average number of bids has been only 1.3 per tract, with losing bidders unable to compete for many tracts due to their need to limit budget exposure. Similarly, recent auctions of mortgage-backed securities have low participation, and buyers are interested in limiting their spending on various types of securities to limit or manage the risks they bear.
Multi-item auction design has been at the frontier of research in economics and computer science, and several new designs have been proposed. Yet none of the new designs enables effective competition in auctions when participants are faced with serious budget constraints and must limit the cost of items acquired. The addition of budget constraints to auctions that exist in the prior art poses a number of problems. One is a problem of computation, which arises because finding auction outcomes can require finding solutions to packing problems. A second problem concerns incentives: the new mechanisms must be thoroughly analyzed to verify that they do not enable collusive behavior or undesirable equilibrium outcomes. While extending simple auctions appears to be straightforward, a third problem involves extending the rules of more complex auctions, such as core-selecting combinatorial auctions.